package ink.lovejinhu.leetcode;

/**
 * @author jinhu
 * created 2021-07-09 16:19
 */
public class Solution_0278 {
    public boolean isBadVersion(int n) {
        return false;
    }

    public int firstBadVersion(int n) {   //isBadVersion(n)~false isBadVersion(n+1)~true
        int left = 1;
        int right = n;
        while (true) {
            if (n == 1) {
                if (isBadVersion(n)) return 1;
                else return 0;
            }
            if (isBadVersion(n)) {  //n是坏的
                if (isBadVersion(n - 1)) {  //证明n的右边全是坏的，
                    n = right + left >> 1;
                    right = n;
                    continue;
                } else {  //n-1是好的
                    return n ;

                }
            } else {  //n是好的
                if (isBadVersion(n + 1)) {   //n+1是坏的
                    return n + 1;
                } else {   //n+1也是好的
                    n = left + right >> 1;
                    left = n;
                }
            }
        }
    }

    public int BaolifirstBadVersion(int n) {
        while (isBadVersion(n)) {
            n--;
        }
        return n + 1;
    }
}
